/* @brief Try to write a KMP implementation (code is from book, of course)
 * @author Stone
 * @date June 2021 at GDOU
 *
 * @note 
 *  For string S, S[0] stores the length of this string,
 *      so the first character is s[1].
 */
#include <stdio.h>


/* @Usage:
 *  char myStr[] = "0abc123";  // the actual string is "abc123"
 *  StrInit(myStr);
 */
#define StrInit(S)  S[0] = (sizeof(S) - 2)
#define Str(S)  &(S[1])


void GetNext(const char * const T, int next[]){
    int i=1, j=0;
    next[1] = 0;

    while (i < T[0]) {
        // 情况1: 前缀字符 T[j] 等于 后缀字符T[j]
        //      - i, j 同步后移, 比较下一个前缀字符和后缀字符是否相等.
        //      - 之所以先后移i,j, 再赋值next[i] = j, 要结合匹配字符串的代码来看.
        //      - 可见, 若i, j处的字符相等, next[i+1]是相等字符位置的下一位j+1, 若
        //        不等, 则next[i+1]是首个字符的索引 1.
        // 情况2: 前缀字符 T[j] 不等 后缀字符T[i]
        //      - i 不变, j 在 j = next[j] 的回溯中逐渐变小, 最小变为0, 然后在下
        //        一次循环中, i后移一位, 而j从1重新开始.
        // 
        // 由此可见, 若模式串T不存在重复结构, 如"abc", 则next[i]分两步变化, 分别在两次循环中完成:
        //      第一步, j为1, 且T[j]不等T[i], 于是 j=next[j], j变为0; 本次循环完成;
        //      第二步, j为0, 于是i,j均后移一位, j变为1, 于是next[i]=1;
        // 于是得到结论:
        //      - 不存在重复结构的模式串T, 所有的next[i](i≠0)的值都是1. (符合定义)
        //      - 进入函数的初始状态j=0, i=1, 可视为从第二步开始.
        //
        // 若模式串中存在重复结构, 容易看出在重复部分, next[i+1]的值, 是与后缀字符T[i]相等
        // 的前缀字符T[j]的后一个位置j+1. 在不重复的部分next[i+1]的值是1, 表示直接回到第一个字符.
        //
        if (0 == j || T[j] == T[i]) {
            i++;
            j++;
            next[i] = j;
        }
        else {
            j = next[j];
        }
    }
}


int IndexKmp(const char * const S, const char * const T, int pos, const int next[]) {
    int i=pos, j=1;
    
    if (i<1) i = 1;

    while (i<=S[0] && j<=T[0]) {
        if (0==j || S[i] == T[j]) {
            i++;
            j++;
        }
        else {
            j = next[j];
        }
    }

    if (T[0] < j && S[0] >= i-1) {
        return i - T[0];
    }
    else {
        return -1;
    }
}


void test_StrInit() {
    // the 0th character is a placeholder.
    char s1[] = "-abc";
    char s2[] = "-12345";
    StrInit(s1);
    StrInit(s2);

    printf("%s, %d\n", Str(s1), s1[0]);
    printf("%s, %d\n", Str(s2), s2[0]);
}


void test_GetNext(){
    char t1[] = "-abcd";
    char t2[] = "-abab";
    char t3[] = "-abcab";
    char t4[] = "-abcxabcyabxbc";
    int next1[sizeof(t1)];
    int next2[sizeof(t2)];
    int next3[sizeof(t3)];
    int next4[sizeof(t4)];

    StrInit(t1);
    StrInit(t2);
    StrInit(t3);
    StrInit(t4);
    GetNext(t1, next1);
    GetNext(t2, next2);
    GetNext(t3, next3);
    GetNext(t4, next4);

    printf("%s\n", Str(t1));
    for (int i=0; i<=t1[0]; i++) {
        printf("%d ", next1[i]);
    }
    
    printf("\n%s\n", Str(t2));
    for (int i=0; i<=t2[0]; i++) {
        printf("%d ", next2[i]);
    }
    
    printf("\n%s\n", Str(t3));
    for (int i=0; i<=t3[0]; i++) {
        printf("%d ", next3[i]);
    }

    printf("\n%s\n", Str(t4));
    for (int i=0; i<=t4[0]; i++) {
        printf("%d ", next4[i]);
    }
    printf("\n");
}


void test_IndexKmp(){
    char s[] = "-abc123abcd1234";
    char t1[] = "-bc";
    char t2[] = "-123";
    int next1[sizeof(t1)];
    int next2[sizeof(t2)];

    StrInit(s);
    StrInit(t1);
    StrInit(t2);

    GetNext(t1, next1);
    GetNext(t2, next2);

    int pos1 = IndexKmp(s, t1, 0, next1);
    int pos2 = IndexKmp(s, t2, 0, next2);

    printf("t:%s, pos: %d \n", Str(t1), pos1);
    printf("t:%s, pos: %d \n", Str(t2), pos2);
}


void main() {
    //test_StrInit();
    //test_GetNext();
    test_IndexKmp();
}
